#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

#define RED 1
#define BLACK 0
#define Color int
#define SPACE " "

template <typename Key,typename Value>
class RedBlackTree{
private:
    struct Node {
        Key key;
        Value value;
        Color color;
        Node *left = NULL;
        Node *right = NULL;
        int N=0;

        Node(Key key, Value value, int N, Color color){
            this->key=key;
            this->value=value;
            this->N = N;
            this->color=color;
        }
    };
    void destory(Node *node){
        if(node==NULL)
            return;
        destory(node->left);
        destory(node->right);
        delete node;
    }

    Node * root;

    Node* rotateLeft(Node * h){
        Node* x = h->right;
        h->right = x->left;
        x->left = h;

        x->color = h->color;
        h->color = RED;

        x->N = h->N;
        h->N = 1+size(h->left)+size(h->right);

        return x;
    }

    Node* rotateRight(Node* h){
        Node* x = h->left;
        h->left = x->right;
        x->right = h;

        x->color = h->color;
        h->color = RED;

        x->N = h->N;
        h->N = 1+size(h->left)+size(h->right);

        return x;
    }
    bool isRed(Node * node){
        if(node == NULL) return false;
        return node->color==RED;
    }

    void filpColors(Node* h){
        h->color=!h->color;
        h->left->color=!h->left->color;
        h->right->color=!h->right->color;
    }

    int size(Node* node){
        if(node==NULL) return 0;
        return node->N;
    }

    Node* put(Node* node, Key key, Value value){
        if(node == NULL)
            return new Node(key,value,1,RED);
        if(node->key>key) {
            node->left = put(node->left, key, value);
//            node->N++;
        }else if(node->key<key){
            node->right = put(node->right,key,value);
//            node->N++;
        }else{
            node->value = value;
        }
        if(!isRed(node->left) && isRed(node->right))
            node = rotateLeft(node);
        if(isRed(node->left) && isRed(node->left->left))
            node = rotateRight(node);
        if(isRed(node->left) && isRed(node->right))
            filpColors(node);
        node->N = 1+size(node->left)+size(node->right);
        return node;
    }

    Node* putAs234Tree(Node* node, Key key, Value value){
        if(node == NULL)
            return new Node(key,value,1,RED);
        if(isRed(node->left) && isRed(node->right)) filpColors(node);
        if(node->key>key) {
            node->left = putAs234Tree(node->left, key, value);
        }else if(node->key<key){
            node->right = putAs234Tree(node->right,key,value);
        }else{
            node->value = value;
        }
        if(!isRed(node->left) && isRed(node->right))
            node = rotateLeft(node);
        if(isRed(node->left) && isRed(node->left->left))
            node = rotateRight(node);
        node->N = 1+size(node->left)+size(node->right);
        return node;
    }

    Node* _moveRedLeft(Node * node){
        filpColors(node);
        if(isRed(node->right->left)){
            node->right = rotateRight(node->right);
            node = rotateLeft(node);
            filpColors(node);
        }
        return node;
    }

    Node* _moveRedRight(Node *node){
        filpColors(node);
        if(isRed(node->left->left)){
            node = rotateRight(node);
            filpColors(node);
        }
        return node;
    }

    Node * _removeMin(Node* node){
        if(node->left == NULL){
            delete node;
            return NULL;
        }
        if(!isRed(node->left) && !isRed(node->left->left)){
            node = _moveRedLeft(node);
        }
        node->left = _removeMin(node->left);
        return _blance(node);
    }

    Node * _removeMax(Node* node){
        //              B
        //            //right = {RedBlackTree<char, char>::Node * | 0xe21270} 0xe21270
        //          A
        if(isRed(node->left))//如果左节点对于红连接，说明是3-节点一部分，那么node右边子树可能为空，这时候需要右旋，使得右边节点不为空
            node = rotateRight(node);
        if(node->right==NULL){
            delete node;
            return NULL;
        }
        if(!isRed(node->right) && !isRed(node->right->left))
            node = _moveRedRight(node);
        node->right = _removeMax(node->right);
        return _blance(node);

    }

    Node* _minNum(Node* node){
        while(node->left){
            node = node->left;
        }
        return node;
    }
    bool _contain(Node * node, Key key){
        if(node == NULL)
            return false;
        if(node->key==key){
            return true;
        }
        if(node->key>key){
            return _contain(node->left,key);
        }
        if(node->key<key){
            return _contain(node->right,key);
        }
    }

    Node* _remove(Node* node, Key key){
        if(key<node->key){
            if(!isRed(node->left) && !isRed(node->left->left)){
                node = _moveRedLeft(node);
            }
            node->left = _remove(node->left,key);
        }else{
            if(isRed(node->left))//如果左节点对于红连接，说明是3-节点一部分，那么node右边子树可能为空，这时候需要右旋，使得右边节点不为空
                node = rotateRight(node);
            if(key == node->key && (node->right==NULL)){
                delete node;
                return NULL;
            }
            if(!isRed(node->right) && !isRed(node->right->left))
                node = _moveRedRight(node);
            if(key == node->key){
                Node* min = _minNum(node->right);
                node->key=min->key;
                node->value=min->value;
                node->right = _removeMin(node->right);
            }else{
                node->right = _remove(node->right,key);
            }
        }
        return _blance(node);
    }

//    void filp4drgee_Colors(Node* h){
//        h->color = BLACK;
//        if(h->right != NULL) h->right->color = RED;
//        if(h->left!=NULL) h->left->color = RED;
//    }

    Node * _blance(Node * node){
        if(!isRed(node->left) && isRed(node->right))
            node = rotateLeft(node);
        if(isRed(node->left) && isRed(node->left->left))
            node = rotateRight(node);
        if(isRed(node->left) && isRed(node->right))
            filpColors(node);
        node->N = 1+size(node->left)+size(node->right);
        return node;
    }

    bool _isBalanced(Node* node, int black){
        if(node==NULL)
            return black==0;
        int nextb = black;
        if(!isRed(node)){
            nextb=black-1;
        }
        return _isBalanced(node->left,nextb) && _isBalanced(node->right,nextb);
    }

    bool _is23(Node* node){
        if(node==NULL) return true;
        if(isRed(node->right)) return false;
        if(isRed(node) && isRed(node->left)) return false;
        return _is23(node->left) && _is23(node->right);
    }

    bool _isBST(Node* node, Key low, Key high){
        if(node == NULL) return true;
        if(low!=NULL && node->key<=low) return false;
        if(high!=NULL && node->key>=high) return false;
        return _isBST(node->left,low,node->key) && _isBST(node->right,node->key,high);
    }

    bool _isSizeConsistent(Node* node){
        if(node == NULL) return true;
        if(node->N!=1+size(node->left)+size(node->right)) return false;
        return _isSizeConsistent(node->right) && _isSizeConsistent(node->left);
    }

    int _rank(Node* node, Key key){
        int rank = 0;
        while(node != NULL){
            int leftCount = node->left==NULL?0:node->left->N;
            if(node->key==key){
                return rank+leftCount;
            }else if(node->key<key){
                rank+=leftCount+1;
                node=node->right;
            }else{
                node=node->left;
            }
        }
        return rank;
    }

    /**
     *
     * @param node 当前节点
     * @param preRank 以node为根节点的树中最小节点的排名
     * @param select
     * @return
     */
    Node* _select(Node* node,int preRank,int select){
        int curentRank = (node->left==NULL?0:node->left->N)+preRank;
        if(select==curentRank){
            return node;
        }else if(select>curentRank){
            return _select(node->right,curentRank+1,select);
        }else{
            return _select(node->left,preRank,select);
        }
    }


    int max_dep(Node* h){
        return h == NULL?0:(max(max_dep(h->right),max(h->left))+1);
    }

    string* _draw(Node* node){
        if(node==NULL){
            return new string(SPACE);
        }
        string* lefts = _draw(node->left);
        int dleft = max_dep(node->left);
        string* rights = _draw(node->right);
        int dright = max_dep(node->right);

        string* merage = NULL;
        int d = dright-dleft;
        if(d>0){
            for(int x = 0;x<d;x++){
                int s1 = dleft+x+1;
                int s2 = s1*2+1;
                for(int j = 0;j<dleft;j++){
                    lefts[j] = muxIString(s1).append(lefts[j]).append(muxIString(s1));
                }

            }
        }

    }

    string muxIString(int i){
        string x = "";
        while(i>=0){
            x.append(SPACE);
            i--;
        }
        return x;
    }

public:
    RedBlackTree(){
        root = NULL;
    }
    ~RedBlackTree(){
        destory(root);
    }
    int size(){
        return size(root);
    }

    void put(Key key,Value value){
        root = put(root,key,value);
//        root = putAs234Tree(root,key,value);
        root->color = BLACK;
    }

    void removeMin(){
        assert(root!=NULL);
        if(!isRed(root->left) && !isRed(root->right)){
            root->color = RED;
        }
        root = _removeMin(root);
        if(!root==NULL) root->color = BLACK;
    }

    void removeMax(){
       assert(root!=NULL);
       if(!isRed(root->left) && !isRed(root->right))
           root->color = RED;
       root = _removeMax(root);
       if(root!=NULL) root->color = BLACK;
    }

    Key* select(int select){
        assert(select>=0 && select<root->N);
        Node* node = _select(root,0,select);
        return &(node->key);
    }

    //小于key的键数量
    int rank(Key key){
        return _rank(root,key);
    }

    void check(){
        if(!isBalanced()) cout<<" isBalanced = false"<<endl;
        if(!is23()) cout<<" is23 = false"<<endl;
        if(!isBST()) cout<<" isBST = false"<<endl;
        if(!isSizeConsistent()) cout<<" isSizeConsistent = false"<<endl;
        if(!isRankConsistent()) cout<<" isRankConsistent = false"<<endl;
        else{
            cout<<" check pass"<<endl;
        }
    }

    bool isBalanced(){
        int black = 0;
        Node* node = root;
        while(node!=NULL){
            if(!isRed(node))
                black++;
            node=node->left;
        }
        return _isBalanced(root,black);
    }

    bool is23(){
        return _is23(root);
    }

    bool isBST(){
        return _isBST(root,NULL,NULL);
    }

    bool isSizeConsistent(){
        return _isSizeConsistent(root);
    }

    bool isRankConsistent() {
        for (int i = 0; i < size(); i++)
            if (i != rank(*select(i))) return false;
        return true;
    }


    void remove(Key key){
        assert(key!=NULL);
        assert(root!=NULL);
        assert(_contain(root,key));
        if(!isRed(root->left) && !isRed(root->right))
            root->color = RED;
        root = _remove(root,key);
        if(root!=NULL) root->color = BLACK;
    }

    void draw(){
        if(max_dep(root)>5){
            throw "support max deep 5";
        }
        _draw(root);
    }
};

int main() {
    RedBlackTree<char,char> redBlackTree;
    char s[] = {'S','E','A','R','C','H','X','M','P','L'};
    for(int i = 0 ; i< 10;i++){
        redBlackTree.put(s[i],s[i]);
    }
//    redBlackTree.check();

//    redBlackTree.removeMin();
//    redBlackTree.removeMin();//can debug _moveRedLeft
//    redBlackTree.removeMin();

//    redBlackTree.removeMax();
//    redBlackTree.removeMax();
//    redBlackTree.removeMax();
//    redBlackTree.removeMax();


    redBlackTree.remove('M');
    redBlackTree.check();
}